package 牛客.字符串;

/*
    题目描述
        给定一个数组arr，返回子数组的最大累加和
        例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
        题目保证没有全为负数的数据
        [要求]
        时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

        示例1     输入   [1, -2, 3, 5, -2, 6, -1]
                 返回值  12
 */
public class 子数组最大累加和问题 {
    public int maxsumofSubarray (int[] arr) {
        // write code here

        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
           arr[i] += arr[i - 1] > 0 ? arr[i - 1] : 0;
           max = Math.max(max, arr[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        子数组最大累加和问题 obj = new 子数组最大累加和问题();
        int arr[] = {1, -2, -3, 4, 5, -1, 3};
        int i = obj.maxsumofSubarray(arr);
        System.out.println(i);
    }
}
